//
// Created by Administrator on 2021/8/3.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    int findLHS(vector<int> &nums) {
        unordered_map<int, int> counter;
        for (auto &x:nums) {
            ++counter[x];
        }
        vector<int> numTypes;
        numTypes.reserve(counter.size());
        for (auto &x:counter) {
            numTypes.push_back(x.first);
        }
        // 排序
        sort(numTypes.begin(), numTypes.end());
        // 相差1的
        int ans = 0;
        for (int i = 1; i < numTypes.size(); ++i) {
            if (numTypes[i - 1] == numTypes[i] - 1) {
                ans = max(ans, counter[numTypes[i - 1]] + counter[numTypes[i]]);
            }
        }
        return ans;
    }
};
class Solution2 {
public:
    int findLHS(vector<int> &nums) {
        unordered_map<int, int> counter;
        for (auto &x:nums) {
            ++counter[x];
        }
        // 在hash表中 找x+1
        int ans = 0;
        for(auto &x:counter){
            if (counter.count(x.first+1)){
                ans = max(ans,x.second+counter[x.first+1]);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> nums{1, 3, 2, 2, 5, 2, 3, 7};
    vector<int> nums1{1, 2, 3, 4};
    vector<int> nums2{1, 1, 1, 1};
    Solution2 solution;
    cout << solution.findLHS(nums) << endl;
    cout << solution.findLHS(nums1) << endl;
    cout << solution.findLHS(nums2) << endl;
    return 0;
}
